package com.zj.sixtyDayChallenge.tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @program: algorithm
 * @description: 二叉树的后序遍历
 * 145 binary-tree-postorder-traversal
 * //给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
 * //
 * //
 * //
 * // 示例 1：
 * //
 * //
 * //输入：root = [1,null,2,3]
 * //输出：[3,2,1]
 * //
 * //
 * // 示例 2：
 * //
 * //
 * //输入：root = []
 * //输出：[]
 * //
 * //
 * // 示例 3：
 * //
 * //
 * //输入：root = [1]
 * //输出：[1]
 * //
 * //
 * //
 * //
 * // 提示：
 * //
 * //
 * // 树中节点的数目在范围 [0, 100] 内
 * // -100 <= Node.val <= 100
 * //
 * //
 * //
 * //
 * // 进阶：递归算法很简单，你可以通过迭代算法完成吗？
 * //
 * // Related Topics 栈 树 深度优先搜索 二叉树 👍 981 👎 0
 * @author: Zhang Bo
 * @create: 2022-01-14 17:05
 **/
public class BinaryTreePostorderTraversal {
    public static void main(String[] args) {
        Solution solution = new BinaryTreePostorderTraversal().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    class Solution {
        public List<Integer> postorderTraversal(TreeNode root) {
            ArrayList<Integer> list = new ArrayList<>();

            if (root == null) {
                return list;
            }
            this.invoke(root, list);
            return list;

        }

        private void invoke(TreeNode root, ArrayList<Integer> list) {
            if (root.left != null) {
                this.invoke(root.left, list);
            }

            if (root.right != null) {
                this.invoke(root.right, list);
            }
            list.add(root.val);
        }


        public List<Integer> after(TreeNode root) {
            List<Integer> list = new ArrayList<>();
            if (root == null) {
                return list;
            }
            Stack<TreeNode> stack = new Stack<>();
            TreeNode prev = null;
            while (root != null || !stack.isEmpty()) {
                while (root != null) {
                    stack.push(root);
                    root = root.left;
                }

                root = stack.pop();
                if(root.right == null || root.right == prev){
                    list.add(root.val);
                    prev = root;
                    root = null;
                } else {
                    stack.push(root);
                    root = root.right;
                }
            }
            return list;

        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
